#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MaxSize 50
typedef int ElemType;
typedef struct SeqList{
    ElemType data[MaxSize];
    int length;
}SeqList;
// 初始化数组：给数组中填充元素
void initList(SeqList &S,int length){
    S.length = length;
    srand(time(NULL));// 生成随机数
    for(int i=0;i<S.length;i++){
        S.data[i] = rand()%100;
    }
}
// 遍历数组中的数据
void printList(SeqList S){
    for (int i = 0; i < S.length; ++i) {
        printf("%d ",S.data[i]);
    }
    printf("\n");
}
// 分区
int Partition(ElemType E[],int low,int high){
    int pivot = E[low];// 用第一个元素作为枢轴
    while(low < high){ // 循环遍历搜索枢轴的位置
        while(low<high && E[high]>= pivot){
            --high; // 右边的数大于枢轴，则右边继续左移
        }
        // 执行到这了，说明右边的数小于枢轴，则移动到左端
        E[low] = E[high];
        while(low < high && E[low] <= pivot) {
            ++low; // 左边的数小于枢轴，则左边继续右移
        }
        // 执行到这了，说明左边的数大于枢轴，则移动到右端
        E[high] = E[low];
    }
    // 当low>=high，说明找到了枢轴的位置
    E[low] = pivot;
    return low;// 返回存放枢轴的位置
}
// 快速排序：从小到大
void QuickSort(ElemType E[],int low,int high){
    if(low < high){
        int pivot = Partition(E,low,high); // 划分
        QuickSort(E,low,pivot-1);// 划分左子表
        QuickSort(E,pivot+1,high); // 划分右子表
    }
}
int main() {
    SeqList S;
    initList(S,10);
    printList(S);
    QuickSort(S.data,0,S.length-1);
    printList(S);
    return 0;
}
